package tree;

/**
 * Created with IntelliJ IDEA.
 * Description: 105. 从前序与中序遍历序列构造二叉树
 * User: Li_yizYa
 * Date: 2025/6/5
 * Time: 14:27
 */
public class Solution24 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 ||
                inorder == null || inorder.length == 0) {
            return null;
        }
        return traversal(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    private TreeNode traversal(int[] preorder, int preorderStart, int preorderEnd,
                               int[] inorder, int inorderStart, int inorderEnd) {
        if (preorderStart == preorderEnd) {
            return null;
        }
        // 取前序第一个元素作为根结点
        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);

        // 根据根结点划分中序数组
        int midIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (rootVal == inorder[i]) {
                midIndex = i;
                break;
            }
        }
        int leftInorderStart = inorderStart;
        int leftInorderEnd = midIndex;
        int rightInorderStart = midIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 划分前序数组
        int leftPreorderStart = preorderStart + 1;
        int leftPreorderEnd = leftPreorderStart + (midIndex - inorderStart);
        int rightPreorderStart = leftPreorderEnd;
        int rightPreorderEnd = preorderEnd;

        root.left = traversal(preorder, leftPreorderStart, leftPreorderEnd,
                inorder, leftInorderStart, leftInorderEnd);
        root.right = traversal(preorder, rightPreorderStart, rightPreorderEnd,
                inorder, rightInorderStart, rightInorderEnd);
        return root;
    }
}
